package com.mgq.algorithm.link;

/**
 * 终极题
 *
 *
 * 给2个链表,这2个链表可能有环,也可能没有环,返回他们相交的第一个节点
 * 有节点,返回节点,无节点返回null
 *
 *
 */
public class TwoLinkedListCycle_Final {
    public static void main(String[] args) {

    }

    /**
     * 给2个链表,这2个链表可能有环,也可能没有环,返回他们相交的第一个节点
     * 有节点,返回节点,无节点返回null
     * @param head1
     * @param head2
     * @return
     */
    public ListNode twoLinkedListCycle(ListNode head1, ListNode head2) {
        if (head1 == null && head2 == null) {
            return null;
        }
        ListNode node1 = detectCycle(head1);
        ListNode node2 = detectCycle(head2);
        if (node1 == null && node2 == null) {
            //处理2个无环链表相交的第一个节点(160题)
           return noLoop(head1,head2);
        }
        //两个都有环
        if (node1 != null && node2 != null) {
         return    bothLoop(head1,node1,head2,node2);
        }
        //注意:单链表不存在,一个有环,一个无环,他们还相交的情况.因为只有一个next指针,只要他们相交,绝对出不来
        return  null;
    }
    public ListNode noLoop(ListNode headA, ListNode headB) {
        int length1=0;
        int length2=0;
        ListNode cur1=headA;
        ListNode cur2=headB;
        //这样不会走到null,只会到最后一个节点
        while (cur1.next != null) {
            length1++;
            cur1=cur1.next;
        }
        while (cur2.next != null) {
            length2++;
            cur2 = cur2.next;
        }
        //表示没有相交
        if (cur1 != cur2) {
            return  null;
        }
        //相交了.找出长度最大的链表
        cur1 = length1 > length2 ? headA : headB;
        cur2 = cur1 == headA ? headB : headA;
        int n = Math.abs(length1 - length2);
        while (n != 0) {
            n--;
            cur1 = cur1.next;
        }
        while (cur1 != cur2) {
            cur1=cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }

    /**
     * 判断一个链表是否有环,有环返回链表的第一个环节点,没有环返回null
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        ListNode slow=head;
        ListNode fast=head;
        while (fast != null && fast.next != null) {
            slow=slow.next;
            fast=fast.next.next;
            //有环
            if (slow == fast) {
                break;
            }
        }
        //有可能没进if,但是没有环
        if (fast == null||fast.next==null) {
            return null;
        }
        //慢指针从头开始
        slow=head;
        while (slow != fast) {
            slow=slow.next;
            fast=fast.next;
        }
        return slow;
    }
    /**
     * 两个有环链表的相交的第一个节点
     * @param head1
     * @param loop1
     * @param head2
     * @param loop2
     * @return
     */
    public ListNode bothLoop(ListNode head1, ListNode loop1, ListNode head2, ListNode loop2) {
        /**
         * 情况1.两个有环链表不相交
         *情况2.两个链表有环,但是他们有环的节点位置一样
         *             o   o
         *             \  /
         *              o
         *            /   \
         *          o <-  o
         *情况3.两个链表有环,但是他们环的开始节点不一样
         *             o
         *             \
         *              o    o
         *             / \  /
         *            o   o
         *           /    \
         *          o <-  o
         *
         */
        //情况2.也就是他们的环的开始节点一样.这时返回他们2个链表的相交节点即可,和环没有关系
        if (loop1 == loop2) {
            int length1 = 0;
            int length2 = 0;
            ListNode cur1 = head1;
            ListNode cur2 = head2;
            //走到环就行,不能继续走,继续就死循环了,也没有必要
            while (cur1.next == loop1) {
                length1++;
                cur1 = cur1.next;
            }
            while (cur2.next == loop1) {
                length2++;
                cur2 = cur2.next;
            }
            cur1 = length1 > length2 ? head1 : head2; //cur1 指向最长的链表
            cur2 = cur1 == head1 ? head2 : head1; //cur2指向最短的链表
            int n = Math.abs(length1 - length2);
            while (n != 0) {
                n--;
                cur1 = cur1.next;
            }
            while (cur1 != cur2) {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return cur1;
        } else {
            //都有环,loop1走一圈,遇到loop2,说明是情况3.否则就是情况1
            ListNode  cur1 = loop1.next;
            //走一圈
            while (cur1 != loop1) {
                if (cur1 == loop2) {
                    //返回cur1或者loop2,因为这2个从不同的角度看,都是2个环的第一个节点
                    return cur1;
                }
                cur1 = cur1.next;
            }
            //情况1
            return null;
        }

    }
}
